//402. 移掉 K 位数字

//给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

//class Solution {
//public:
//    string removeKdigits(string num, int k) {
//        vector<char> stk;
//        for (auto& digit : num) {
//            while (stk.size() > 0 && stk.back() > digit && k) {
//                stk.pop_back();
//                k--;
//            }
//            stk.push_back(digit);
//        }
//
//        for (; k > 0; --k) {
//            stk.pop_back();
//        }
//
//        string ans = "";
//        bool isLeadingZero = true;
//        for (auto& digit : stk) {
//            if (isLeadingZero && digit == '0') {
//                continue;
//            }
//            isLeadingZero = false;
//            ans += digit;
//        }
//        return ans == "" ? "0" : ans;
//    }
//};

//1673. 找出最具竞争力的子序列

//给你一个整数数组 nums 和一个正整数 k ，返回长度为 k 且最具 竞争力 的 nums 子序列。
//数组的子序列是从数组中删除一些元素（可能不删除元素）得到的序列。
//在子序列 a 和子序列 b 第一个不相同的位置上，如果 a 中的数字小于 b 中对应的数字，那么我们称子序列 a 比子序列 b（相同长度下）更具 竞争力 。 
//例如，[1, 3, 4] 比[1, 3, 5] 更具竞争力，在第一个不相同的位置，也就是最后一个位置上， 4 小于 5 。

//class Solution {
//public:
//    vector<int> mostCompetitive(vector<int>& nums, int k) {
//        vector<int> st;
//        for (int i = 0; i < nums.size(); i++) {
//            int x = nums[i];
//            while (!st.empty() && x < st.back() && st.size() + nums.size() - i > k) {
//                st.pop_back();
//            }
//            if (st.size() < k) {
//                st.push_back(x);
//            }
//        }
//        return st;
//    }
//};

//316. 去除重复字母

//给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

//class Solution {
//public:
//    string removeDuplicateLetters(string s) {
//        int left[26]{};
//        for (char c : s) {
//            left[c - 'a']++; // 统计每个字母的出现次数
//        }
//
//        string ans;
//        bool in_ans[26]{};
//        for (char c : s) {
//            left[c - 'a']--;
//            if (in_ans[c - 'a']) {
//                continue;
//            }
//            while (!ans.empty() && c < ans.back() && left[ans.back() - 'a']) {
//                in_ans[ans.back() - 'a'] = false;
//                ans.pop_back();
//            }
//            ans += c;
//            in_ans[c - 'a'] = true;
//        }
//        return ans;
//    }
//};

//Q3. 整理书架

//书架上有若干本书，从左至右的书籍编号记于整型数组 order 中。为保证书籍多样性，管理员想取走一些重复编号的书籍，要求满足以下条件：
//剩余书本中相同编号的书本数量均不大于 limit
//取走的书籍数量尽可能少
//由于存在多种整理方案，请返回剩余书本编号的排列为「最小排列」的方案。
//注意：
//「最小排列」：若干数组中第一位数字最小的数组；若第一位数字相同，则为第二位数字最小的数组，以此类推。

//class Solution {
//public:
//    vector<int> arrangeBookshelf(vector<int>& order, int limit) {
//        unordered_map<int, int> left;  // 不在答案中的
//        unordered_map<int, int> right; // 在答案中的
//        for (int& x : order) {
//            right[x]++;
//        }
//
//        vector<int> ans;
//        for (int& x : order) {
//            if (left[x] == limit) { // 已经满了，不再添加
//                right[x]--;
//                continue;
//            }
//            // 前面有比当前数大且前面的数量大于limit，可以删除
//            while (!ans.empty() && ans.back() > x && left[ans.back()] + right[ans.back()] > limit) {
//                left[ans.back()]--;
//                ans.pop_back();
//            }
//            right[x]--;
//            left[x]++;
//            ans.push_back(x);
//        }
//        return ans;
//    }
//};

//321. 拼接最大数

//给你两个整数数组 nums1 和 nums2，它们的长度分别为 m 和 n。数组 nums1 和 nums2 分别代表两个数各位上的数字。同时你也会得到一个整数 k。
//请你利用这两个数组中的数字创建一个长度为 k <= m + n 的最大数。同一数组中数字的相对顺序必须保持不变。
//返回代表答案的长度为 k 的数组。

//class Solution {
//public:
//    vector<int> get_length(int len, vector<int>& arr) {
//        int n = arr.size();
//        vector<int> s;
//        for (int i = 0; i < n; i++) {
//            int x = arr[i];
//            // 如果满足弹栈条件->把栈顶弹了后面的元素全进来的所有值的个数大于等于所需总长度
//            while (s.size() && x > s.back() && s.size() + n - i - 1 >= len) {
//                s.pop_back();
//            }
//            s.push_back(x);
//        }
//        while (s.size() > len) { // 由于是单调递减栈，后面可能会多出元素
//            s.pop_back();
//        }
//        return s;
//    }
//
//    vector<int> merge_sort(vector<int>& a, vector<int>& b) {
//        int n = a.size(), m = b.size();
//        a.push_back(-1), b.push_back(-2);
//        vector<int> ans;
//        int p1 = 0, p2 = 0;
//        while (p1 < n || p2 < m) {
//            if (p2 >= m || (p1 < n && a[p1] > b[p2])) {
//                ans.push_back(a[p1++]);
//            }
//            else if (a[p1] == b[p2]) { // 相等时找到第一个不等元素，由于设立哨兵，因此一定有解
//                for (int i = p1, j = p2; i <= n && j <= m; i++, j++) {
//                    if (a[i] == b[j]) {
//                        continue;
//                    }
//                    if (a[i] < b[j]) {
//                        ans.push_back(b[p2++]);
//                        break;
//                    }
//                    else {
//                        ans.push_back(a[p1++]);
//                        break;
//                    }
//                }
//            }
//            else {
//                ans.push_back(b[p2++]);
//            }
//        }
//        return ans;
//    }
//
//    vector<int> get_max(vector<int>& a, vector<int>& b) {
//        for (int i = 0, n = a.size(); i < n; i++) { // 此处a，b长度必定相等
//            if (a[i] == b[i]) {
//                continue;
//            }
//            if (a[i] > b[i]) {
//                return a;
//            }
//            else {
//                return b;
//            }
//        }
//        return a;
//    }
//
//    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
//        int n = nums1.size(), m = nums2.size();
//        vector<int> ans(k, 0);
//        for (int len1 = 0; len1 <= min(n, k); len1++) {
//            int len2 = k - len1;
//            if (len2 > m) {
//                continue;
//            }
//            vector<int> a = get_length(len1, nums1); // 获取长度为len1的序列
//            vector<int> b = get_length(len2, nums2); // 获取长度为len2的序列
//            vector<int> c = merge_sort(a, b);        // 合并a, b
//            ans = get_max(ans, c);                   // 取所有可能中最大的
//        }
//        return ans;
//    }
//};

//2030. 含特定字母的最小子序列

//给你一个字符串 s ，一个整数 k ，一个字母 letter 以及另一个整数 repetition 。
//返回 s 中长度为 k 且 字典序最小 的子序列，该子序列同时应满足字母 letter 出现 至少 repetition 次。生成的测试用例满足 letter 在 s 中出现 至少 repetition 次。
//子序列 是由原字符串删除一些（或不删除）字符且不改变剩余字符顺序得到的剩余字符串。
//字符串 a 字典序比字符串 b 小的定义为：在 a 和 b 出现不同字符的第一个位置上，字符串 a 的字符在字母表中的顺序早于字符串 b 的字符。

//class Solution {
//public:
//    string smallestSubsequence(string s, int k, char letter, int repetition) {
//        int n = s.size();
//        vector<int> left(n + 1, 0);
//        for (int i = n - 1; i >= 0; i--) {
//            left[i] = left[i + 1] + (s[i] == letter ? 1 : 0);
//        }
//
//        stack<char> st;
//        int cnt = 0;
//        for (int i = 0; i < n; i++) {
//            while (!st.empty() && st.top() > s[i]) {
//                if (st.size() + (n - i) <= k) {
//                    break;
//                }
//                int red = (st.top() == letter) ? 1 : 0;
//                if (cnt - red + left[i] < repetition) {
//                    break;
//                }
//                cnt -= red;
//                st.pop();
//            }
//
//            if (st.size() < k) {
//                if (s[i] == letter) {
//                    st.push(s[i]);
//                    cnt++;
//                }
//                else {
//                    int x = st.size() - cnt;
//                    if (x < k - repetition) {
//                        st.push(s[i]);
//                    }
//                }
//            }
//        }
//
//        while (st.size() > k) {
//            if (st.top() == letter) {
//                cnt--;
//            }
//            st.pop();
//        }
//
//        string ans;
//        while (!st.empty()) {
//            ans += st.top();
//            st.pop();
//        }
//        reverse(ans.begin(), ans.end());
//        return ans;
//    }
//};